package brinaryTree;

import java.util.Stack;

public class N112_PathSun {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        return traversal(root, targetSum - root.val);
    }

    private boolean traversal(TreeNode node, int count) {
        if (node.left == null && node.right == null && count == 0) return true;
        if (node.left == null && node.right == null) return false;

        if (node.left != null) {
            count -= node.val;
            if (traversal(node.left, count)) return true;
            count += node.val;
        }

        if (node.right != null) {
            count -= node.val;
            if (traversal(node.right, count)) return true;
            count += node.val;
        }

        return false;
    }
}
